/*
 * Copyright 2010 - 2011, The PLDesktop Development Team
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 2.1 of the License, or (at your option) any later version.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 *
 */
#ifndef PLHASHTABLE_H
#define PLHASHTABLE_H

#include <PLExceptionBase.h>
#include <tools/PLIEnumerator.h>
#include <tools/PLArray.h>
#include <tools/PLHashTableKeyEnumerator.h>
#include <tools/PLHashTableEnumerator.h>
#ifndef PLHASHTABLE_DISABLE_PLOBJECT
#include <kernel/PLObject.h>
#endif
#include <kernel/lang/PLHash.h>
#include <exception/PLIndexOutOfRangeException.h>
#include <exception/PLElementNotFoundException.h>

namespace PLSDK {

    /**
     * HashTable objects.
     */
    template < typename hashkey, typename hashvalue >
    class PLAPI_EXPORT PLHashTable :
#ifndef PLHASHTABLE_DISABLE_PLOBJECT
        public PLObject,
#endif
        public PLIEnumerator < hashkey, hashvalue > {
    public:
        /**
         * Constructor.
         *
         * @param hashSize The start size of the hashtable and the size that was added to
         * the size if there was not enough space.
         */
        PLHashTable(pluint hashSize = 10);
        /**
         * Destructor.
         */
        ~PLHashTable();
        /**
         * Contains the hashtable the key.
         *
         * @param key The key to test for.
         * @return True if the hashtable contains the key.
         */
        inline plbool containsKey(hashkey key);
        /**
         * Contains the hashtable the value.
         *
         * @param value The value to test for.
         * @return True if the hashtable contains the value.
         */
        inline plbool contains(hashvalue value);
        /**
         * The number of elements in the hashtable.
         *
         * @return The number of elements in the hashtable.
         */
        inline pluint count();
        /**
         * Get a value for a key.
         *
         * @param key The key to find the value for.
         * @return The value for the key.
         * @exception PLElementNotFoundException The element for the key was not found.
         */
        inline hashvalue get(hashkey key);
        /**
         * Get a value for a key.
         *
         * @param key The key to find the value for.
         * @return The value for the key.
         * @exception PLElementNotFoundException The element for the key was not found.
         */
        inline hashvalue value(hashkey key);
        /**
         * Get the enumerator for the values.
         *
         * @return The enumerator for the value values.
         */
        inline PLHashTableEnumerator < hashkey, hashvalue > valueEnumerator();
        /**
         * Get the enumerator for the keys.
         *
         * @return The enumerator for the value keys.
         */
        inline PLHashTableKeyEnumerator < hashkey, hashvalue > keyEnumerator();
        /**
         * Is there a next object.
         *
         * @param pos The current position.
         * @return True if there exists a next object.
         */
        inline plbool hasNext(pluint pos);
        /**
         * Is there a previous object.
         *
         * @param pos The current position.
         * @return True if there exists a previous object.
         */
        inline plbool hasPrevious(pluint pos);
        /**
         * Get the next key object.
         *
         * @param pos The current position.
         * @return The next key object.
         * @exception PLIndexOutOfRangeException The element was not found.
         */
        inline hashkey nextKey(pluint &pos);
        /**
         * Get the previous key object.
         *
         * @param pos The current position.
         * @return The previous key object.
         * @exception PLIndexOutOfRangeException The element was not found.
         */
        inline hashkey previousKey(pluint &pos);
        /**
         * Get the next object.
         *
         * @param pos The current position.
         * @return The next object.
         * @exception PLIndexOutOfRangeException The element was not found.
         */
        inline hashvalue next(pluint &pos);
        /**
         * Get the previous object.
         *
         * @param pos The current position.
         * @return The previous object.
         * @exception PLIndexOutOfRangeException The element was not found.
         */
        inline hashvalue previous(pluint &pos);
        /**
         * Get the first element in the hash. This was not the first inserted value.
         *
         * @return The first element in the hash.
         * @exception PLElementNotFoundException The element for the key was not found.
         */
        inline hashvalue first();
        /**
         * Get the last element in the hash. This is not the last inserted value.
         *
         * @return The last element in the hash.
         * @exception PLElementNotFoundException The element for the key was not found.
         */
        inline hashvalue last();
        /**
         * Add a new entry to the hashtable.
         *
         * @param key The key to add.
         * @param value The value for the key to add.
         */
        inline void put(hashkey &key, hashvalue &value);
        /**
         * Add a new entry to the hashtable.
         *
         * @param key The key to add.
         * @param value The value for the key to add.
         */
        inline void insert(hashkey key, hashvalue value);
        /**
         * Remove a key from the hashtable.
         *
         * @param key The key to remove from the hashtable.
         * @exception PLElementNotFoundException The element for the key was not found.
         */
        inline hashvalue remove(hashkey key);
        /**
         * Remove all elements from the hashtable.
         */
        inline void removeAll();
        /**
         * The size of in the hashtable.
         *
         * @return The size of in the hashtable.
         */
        inline pluint size();
        /**
         * Get a array with all key values.
         *
         * @return The keys of the hashtable.
         */
        inline PLArray<hashkey> keys();
        /**
         * Get a array with all values.
         *
         * @return The values of the hashtable.
         */
        inline PLArray<hashvalue> values();
        /**
         * Get the hash value of the object.
         *
         * @return The hash value of the object.
         * @todo implement a better generaten of a hash value.
         */
        inline virtual pluint hash() const;
#ifndef PLHASHTABLE_DISABLE_PLOBJECT
        /**
         * Compare to objects.
         *
         * @param object Object to compare with.
         * @return The result of the compare.
         * @todo implement the compare
         */
        inline virtual PLCompareResult compareTo(PLObject *object);
#endif
        /**
         * Get a value from the hashtable.
         */
        inline const hashvalue &operator[](hashkey pos) const;
        /**
         * Get a value from the hashtable.
         */
        inline hashvalue &operator[](hashkey pos);
    private:
        inline void addEntry(hashkey key, hashvalue value);
        inline pluint getHashValue(hashkey &key) const;
        inline void rehash();
        inline pluint findKey(hashkey key) const;
        class Entry {
        public:
            hashkey key;
            hashvalue value;
        };
        inline Entry *nextEntry(pluint &pos) {
            if(pos < m_table.size()) {
                for(pluint i = pos ; i < m_table.size() ; i++) {
                    if(m_table[i] != 0) {
                        pos = i + 1;
                        return m_table[i];
                    }
                }
            }
            plthrow(PLIndexOutOfRangeException, plthrowEmpty());
            return 0;
        }
        inline Entry *previousEntry(pluint &pos) {
            for(pluint i = pos ; i != 0 ; i--) {
                if(m_table[i] != 0) {
                    pos = i - 1;
                    return m_table[i];
                }
            }
            plthrow(PLIndexOutOfRangeException, plthrowEmpty());
            return 0;
        }
        PLArray<Entry *> m_table;
        pluint m_count;
        pluint m_hashsize;
    };

    template < typename hashkey, typename hashvalue >
    PLHashTable<hashkey, hashvalue>::PLHashTable(pluint hashSize) :
#ifndef PLHASHTABLE_DISABLE_PLOBJECT
        PLObject(),
#endif
        m_table(hashSize), m_count(0), m_hashsize(hashSize) {
        for(pluint i = 0 ; i < hashSize ; i++) {
            m_table[i] = 0;
        }
    }

    template < typename hashkey, typename hashvalue >
    PLHashTable<hashkey, hashvalue>::~PLHashTable() {
        for(pluint i = 0 ; i < m_table.size() ; i++) {
            delete m_table[i];
        }
    }

    template < typename hashkey, typename hashvalue >
    plbool PLHashTable<hashkey, hashvalue>::containsKey(hashkey key) {
        pltry {
            return findKey(key) >= 0;
        } plexcept {
            plcatch(PLElementNotFoundException) {
                return false;
            }
        }
    }

    template < typename hashkey, typename hashvalue >
    plbool PLHashTable<hashkey, hashvalue>::contains(hashvalue _value) {
        PLHashTableEnumerator < hashkey, hashvalue > en = valueEnumerator();
        while(en.hasNext()) {
            if(en.next() == _value) {
                return true;
            }
        }
        return false;
    }

    template < typename hashkey, typename hashvalue >
    pluint PLHashTable<hashkey, hashvalue>::count() {
        return m_count;
    }

    template < typename hashkey, typename hashvalue >
    hashvalue PLHashTable<hashkey, hashvalue>::get(hashkey key) {
        pluint index = findKey(key);
        if(m_table[index] != 0) {
            return m_table[index]->value;
        }
        plthrow(PLElementNotFoundException, plthrowEmpty());
        return hashvalue();
    }

    template < typename hashkey, typename hashvalue >
    hashvalue PLHashTable<hashkey, hashvalue>::value(hashkey key) {
        return get(key);
    }

    template < typename hashkey, typename hashvalue >
    PLHashTableEnumerator < hashkey, hashvalue > PLHashTable<hashkey, hashvalue>::valueEnumerator() {
        return PLHashTableEnumerator < hashkey, hashvalue >(this);
    }

    template < typename hashkey, typename hashvalue >
    PLHashTableKeyEnumerator < hashkey, hashvalue > PLHashTable<hashkey, hashvalue>::keyEnumerator() {
        return PLHashTableKeyEnumerator < hashkey, hashvalue >(this);
    }

    template < typename hashkey, typename hashvalue >
    plbool PLHashTable<hashkey, hashvalue>::hasNext(pluint pos) {
        for(pluint i = pos ; i < m_table.size() ; i++) {
            if(m_table[i] != 0) {
                return true;
            }
        }
        return false;
    }

    template < typename hashkey, typename hashvalue >
    plbool PLHashTable<hashkey, hashvalue>::hasPrevious(pluint pos) {
        for(pluint i = pos ; i != 0 ; i--) {
            if(m_table[i] != 0) {
                return true;
            }
        }
        return false;
    }

    template < typename hashkey, typename hashvalue >
    hashkey PLHashTable<hashkey, hashvalue>::nextKey(pluint &pos) {
        return nextEntry(pos)->key;
    }

    template < typename hashkey, typename hashvalue >
    hashkey PLHashTable<hashkey, hashvalue>::previousKey(pluint &pos) {
        return previousEntry(pos)->key;
    }

    template < typename hashkey, typename hashvalue >
    hashvalue PLHashTable<hashkey, hashvalue>::next(pluint &pos) {
        return nextEntry(pos)->value;
    }

    template < typename hashkey, typename hashvalue >
    hashvalue PLHashTable<hashkey, hashvalue>::previous(pluint &pos) {
        return previousEntry(pos)->value;
    }

    template < typename hashkey, typename hashvalue >
    hashvalue PLHashTable<hashkey, hashvalue>::first() {
        for(pluint i = 0 ; i < m_table.size() ; i++) {
            if(m_table[i] != 0) {
                return m_table[i]->value;
            }
        }
        plthrow(PLElementNotFoundException, plthrowEmpty());
    }

    template < typename hashkey, typename hashvalue >
    hashvalue PLHashTable<hashkey, hashvalue>::last() {
        for(pluint i = m_table.size() - 1 ; i >= 0 ; i--) {
            if(m_table[i] != 0) {
                return m_table[i]->value;
            }
        }
        plthrow(PLElementNotFoundException, plthrowEmpty());
    }

    template < typename hashkey, typename hashvalue >
    void PLHashTable<hashkey, hashvalue>::put(hashkey &key, hashvalue &_value) {
        pluint index;
        pltry {
            index = findKey(key);
            m_table[index]->value = _value;
        } plexcept {
            plcatch(PLElementNotFoundException) {
                PLUNUSED(e);
                addEntry(key, _value);
            }
        }
    }

    template < typename hashkey, typename hashvalue >
    void PLHashTable<hashkey, hashvalue>::insert(hashkey key, hashvalue _value) {
        put(key, _value);
    }

    template < typename hashkey, typename hashvalue >
    hashvalue PLHashTable<hashkey, hashvalue>::remove(hashkey key) {
        pluint index;
        index = findKey(key);
        hashvalue ret;
        if(index >= 0) {
            ret = m_table[index]->value;
            delete m_table[index];
            m_table[index] = 0;
            m_count--;
        }
        return ret;
    }

    template < typename hashkey, typename hashvalue >
    void PLHashTable<hashkey, hashvalue>::removeAll() {
        for(pluint i = 0 ; i < m_table.size() ; i++) {
            if(m_table[i]) {
                delete m_table[i];
                m_table[i] = 0;
            }
        }
    }

    template < typename hashkey, typename hashvalue >
    PLArray<hashkey> PLHashTable<hashkey, hashvalue>::keys() {
        PLArray<hashkey> ret(m_count);
        pluint pos = 0;
        for(pluint i = 0 ; i < m_table.size() ; i++) {
            if(m_table[i] != 0) {
                ret[pos] = m_table[i]->key;
                pos++;
            }
        }
        return ret;
    }

    template < typename hashkey, typename hashvalue >
    PLArray<hashvalue> PLHashTable<hashkey, hashvalue>::values() {
        PLArray<hashvalue> ret(m_count);
        pluint pos = 0;
        for(pluint i = 0 ; i < m_table.size() ; i++) {
            if(m_table[i] != 0) {
                ret[pos] = m_table[i]->value;
                pos++;
            }
        }
        return ret;
    }

    template < typename hashkey, typename hashvalue >
    pluint PLHashTable<hashkey, hashvalue>::size() {
        return m_table.size();
    }

    template < typename hashkey, typename hashvalue >
    pluint PLHashTable<hashkey, hashvalue>::hash() const {
        return 2;
    }

#ifndef PLHASHTABLE_DISABLE_PLOBJECT
    template < typename hashkey, typename hashvalue >
    PLCompareResult PLHashTable<hashkey, hashvalue>::compareTo(PLObject *object) {
        PLUNUSED(object)
        return PLCompareResultSame;
    }
#endif

    template < typename hashkey, typename hashvalue >
    void PLHashTable<hashkey, hashvalue>::addEntry(hashkey key, hashvalue _value) {
        if(m_table.size() == 0) {
            rehash();
        }
        pluint index = getHashValue(key);
        while(m_table[index] != 0) {
            index++;
            if(index >= m_table.size()) {
                rehash();
                addEntry(key, _value);
                return;
            }
        }
        m_table[index]          = new Entry;
        m_table[index]->key     = key;
        m_table[index]->value 	= _value;
        m_count++;
    }

    template < typename hashkey, typename hashvalue >
    pluint PLHashTable<hashkey, hashvalue>::getHashValue(hashkey &key) const {
        if(m_table.size() == 1) {
            return 0;
        }
        pluint _hash = plHash(key);
        return _hash % m_table.size();
    }

    template < typename hashkey, typename hashvalue >
    void PLHashTable<hashkey, hashvalue>::rehash() {
        PLArray<Entry *> oldEntries(m_table, true);
        m_table.resetSizeOfArray(m_table.size() + m_hashsize);
        for(pluint i = 0 ; i < m_table.size() ; i++) {
            m_table[i] = 0;
        }
        pluint temp = 0;
        for(pluint index = 0 ; index < oldEntries.size(); index++) {
            if(oldEntries[index] != 0) {
                temp = getHashValue(oldEntries[index]->key);
                while(m_table[temp] != 0) {
                    temp++;
                    if(temp >= m_table.size()) {
                        // If there was not space to insert all entry's after rehash we must make a second rehash.
                        // This come in some situations if the hash values are from many objects high and the same or
                        // near by. I hope this was not called so often.
                        for(pluint i = 0 ; i < oldEntries.size() ; i++) {
                            m_table[i] = oldEntries[i];
                        }
                        for(pluint i = oldEntries.size() - 1 ; i < m_table.size() ; i++) {
                            m_table[i] = 0;
                        }
                        rehash();
                        return;
                    }
                }
                m_table[temp] = oldEntries[index];
            }
        }
    }

    template < typename hashkey, typename hashvalue >
    pluint PLHashTable<hashkey, hashvalue>::findKey(hashkey key) const {
        if(m_count == 0) {
            plthrow(PLElementNotFoundException, plthrowEmpty());
        }
        pluint index = getHashValue(key);
        while(index < m_table.size()) {
            if(m_table[index] != 0) {
                if(m_table[index]->key == key) {
                    return index;
                }
            }
            index++;
        }
        plthrow(PLElementNotFoundException, plthrowEmpty());
        return 0;
    }

    template < typename hashkey, typename hashvalue >
    const hashvalue &PLHashTable<hashkey, hashvalue>::operator[](hashkey pos) const {
        return get(pos);
    }

    template < typename hashkey, typename hashvalue >
    hashvalue &PLHashTable<hashkey, hashvalue>::operator[](hashkey key) {
        if(m_table.size() == 0) {
            rehash();
        }
        pluint index = getHashValue(key);
        while(m_table[index] != 0) {
            index++;
            if(index >= m_table.size()) {
                rehash();
                index = getHashValue(key);
            }
        }
        m_table[index]			= new Entry;
        m_table[index]->key 	= key;
        m_count++;
        return m_table[index]->value;
    }

}

#endif
